package com.yangzhe.algorithm.c037;

// 验证平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/
public class Code04_BalancedBinaryTree_LeetCode {

    public static void main(String[] args) {
        TreeNode node = new TreeNode();
        node.val = 1;


        System.out.println(isBalanced(node));
    }

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static boolean result = true;


    /**
     * 平衡二叉树：所有节点左右子树的高度相差<=1
     * <p>
     * 思路：递归遍历
     * 1. 递归左右两颗子树的高度
     * 2. 递归过程中对比左右子树，只要有一个分支不是平衡二叉树，则整棵树就不是平衡二叉树
     *
     * @param root
     * @return
     */
    public static boolean isBalanced(TreeNode root) {
        result = true;
        if (root == null) {
            return result;
        }
        height(root);

        return result;
    }

    public static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // 因为递归过程只有把result改为false的地方，只要有一个分支是false就不是平衡二叉树，这里return什么都不重要了，
        if (Math.abs(leftHeight - rightHeight) > 1) {
            result = false;
            return 0;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

}
